1. Field of the Invention
The present invention is related to the decompression of data which has been previously compressed for transmission or storage and, more particularly, to a system for producing display data from encoded data which has been compressed according to the CCITT Group 4 two-dimensional encoding scheme.
2. Description of the Related Art
There are many known techniques for compressing data without any loss of information. For example, frequently occurring strings can be replaced by a code having a shorter length and less frequently occurring strings can be replaced by a code having a longer length so that the total length of a compressed block of data is smaller than the number of strings times the average length of the codes used to replace the strings. This is essentially the technique known as Huffman coding.
When the number of possible strings is very large, such as in the facsimile transmission, Modified Huffman coding is used to reduce the number of codes required to encode or decode a block of data. The Consultative Committe for International Telegraph and Telephone (CCITT) has established standards for document facsimile machines known as Group 3 and Group 4 which use Modified Huffman coding for at least the first line of a page to replace a string or series of binary digits having the same value (0 or 1, representing white and black, respectively) with a Modified Huffman code. These codes are known as horizontal codes which provide one-dimensional compression.
Two-dimensional compression is implemented on Group 3 and Group 4 machines using Relative Element Address Designate (READ) codes which are modified in Group 3 machines to require insertion of a horizontal encoded (one-dimensional compressed) line every K lines. The two-dimensional compression used on Group 4 machines is known as Modified Modified READ (MMR) which does not require any lines, other than the first, to contain only horizontally compressed codes, nor are end of line (EOL) delimiters used. While Group 4 compression techniques result in a much smaller compressed data block, the effects of a single bit in error is much greater than in Group 3 compression. As a result, the MMR coding scheme (Group 4) is presently used primarily with low error transmission lines, such as in a local area network.
Recommendation T.6 by the CCITT, which is incorporated herein by reference, sets forth the principles of the MMR coding scheme used in Group 4 machines. In a facsimile machine, a document which may contain both text and graphics is digitized using picture elements (pixels or pels) typically running horizontally across a page in a scan line typically having a length of 1728 pixels. The MMR coding scheme allows for much longer run lengths and includes a single code which represents 2623 pels having the same "color" (black or white). In Recommendation T.6, the MMR coding scheme is described with reference to "changing elements" which have a color that is different from the immediately previous element (pixel) along the same scan line and figures similar to FIGS. 1A-1C are used in Recommendation T.6 explain the MMR coding scheme. A brief description of the MMR coding scheme is described below with reference to FIGS. 1A-1C and Tables 1-3, respectively. In Tables 1-3, a "0" bit represent a white pixel and a " 1" bit represents a black pixel. Tables 1-3 are used to emphasize that the MMR coding scheme and other similar compression techniques are applicable, not only to a digitized visual image transmitted between facsimile machines, but also to any form of digital data, including applications where each "pixel" has more than two possible values.
According to Recommendation T.6, the first scan line is defined using horizontal codes. Subsequent lines are defined using vertical codes and pass codes when possible and horizontal codes when necessary. Horizontal codes come in pairs of a white series immediately followed by a black series or a black series immediately followed by a white series.
TABLE 1 ______________________________________ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ______________________________________ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 ______________________________________
Using the example in FIG. 1A and Table 1, the second line would be encoded using horizontal codes for a white series of five elements followed by a black series of six elements. The pixels indicated by a.sub.0, a.sub.1 and a.sub.2 are known as changing elements, where the pixel to the left of a.sub.0 is an imaginary white pixel (represented by "0") preceding the scan line. Using the codes defined in Recommendation T.6, the second line of the example in FIG. 1A and Table 1 would be encoded, using horizontal codes, as "001"+M(a.sub.0 a.sub.1)+M(a.sub.1 a.sub.2), wherein "001" indicates that a pair of horizontal codes follow, M(a.sub.0 a.sub.1) would be replaced with "1100" indicating a white ("0") run length of five pixels (or bits) and M(a.sub.1 a.sub.2) would be replaced with "0010" indicating a black ("1") run length of six. The spaces and quotation marks are not included in the actual codes, and "+" merely indicates concatenation of the various codes.
When data is encoded using the MMR coding scheme described in Recommendation T.6, there is extensive use of two-dimensional codes, i.e., vertical codes and pass codes. Typical documents transmitted by facsimile have a significant amount of vertical correlation permitting vertical codes and pass codes to be used the majority of the time. Two situations where vertical codes are used are illustrated in FIG. 1B and Table 2. The pixel indicated by a.sub.0 is a reference position on a current scan line.
TABLE 2 ______________________________________ 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ______________________________________ 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 ______________________________________
The reference position a.sub.0 is previously defined by, e.g., a horizontal or pass code. By using the first line in FIG. 1A and Table 2 as a reference line, the position (26) of the pixel labeled a.sub.1 can be defined as two pixels to the left of pixel b.sub.1 (position 28) on the reference line. Pixel b.sub.1 is the first color changing pixel to occur after the reference position on the immediately previous scan line. The code which is used is referred to as a V.sub.L (2) code and is represented by "000010". The position (33) indicated by a.sub.2 can be defined as one pixel to the right of the next white-colored changing element (b.sub.2) on the immediately previous or reference scan line. Thus, the next code for the current scan line would be the V.sub.R (1) code which is "011". There are seven possible vertical codes defined in Recommendation T.6 and they permit defining any point on the current scan line in terms of a color changing pixel on the reference line having the same color and being within three pixels. When the color changing pixels are aligned vertically, a V(0) code is used and pixels offset by three to the left and right are defined using codes referred to as V.sub.L (3) and V.sub.R (3), respectively.
In some situations, such as at the bottom of a letter in facsimile encoded text, a series of pixels will exist on the reference line with no corresponding run on the current line. In this case, a pass code is used to indicate that a series of pixels on the current scan line should be generated upon decoding without any change in the color of the pixel occurring at the end of the series. In the example illustrated in FIG. 1C and Table 3, a pass code is generated to skip from a.sub.0 to a.sub.0 ' by skipping or passing the black run which starts at the pixel indicated b.sub.1 (position 54). The pass code is referred to as a P code and is represented by the binary code "0001". In this case, a series of seven white pixels or "0" bits would be generated upon decoding the pass code and then three more white pixels or zeros would be generated in decoding the next code which would be a V.sub.L (2) code.
TABLE 3 ______________________________________ 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 ______________________________________ 0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 ______________________________________
The use of vertical and pass codes significantly reduces the amount of space required to represent the document. However, decoding becomes much more difficult since it is necessary to save information regarding the reference line. When each scan line is over 2500 pixels long, a not insignificant amount of storage is required. Conventional systems for decompressing data encoded using two-dimensional codes, such as MMR, typically use random access memory (RAM) to store an entire decompressed reference line and a decompressed current scan line. A two-dimensional coding scheme which is different from that in Recommendation T.6 is decoded in a system taught by U.S. Pat. No. 4,040,093 to Nakagome et al. which stores only information change pixels, but uses one memory to represent the reference line and another memory to represent the current scan line. Thus, it is necessary to transfer the data from the current scan line memory to the reference line memory each time the decoding of the scan line is completed. As a result, prior art decompression circuits are slowed due to manipulation of the data required to decode two-dimensional codes. To counter this inherent slowness, many decompression systems are implemented entirely in hardware which makes it difficult to adapt such systems to decompress data using different coding schemes.